---
id: 平衡二叉树
title: 平衡二叉树
---

## AVL 树
- AVL树实现ADT Map，基本上与 BST的实现相同，不同之处仅在于二叉树的生成与维护过程。
- AVL树的实现中，需要对每个节点都添加一个数字来反应子节点的深度，我们管这个数字叫做平衡因子（balance factor）。

:::tip 平衡因子
平衡因子是根据节点的左右子树的高度来定义的，确切地说，是左右子树高度差。  
balanceFactor = height(leftSubTree) − height(rightSubTree)   
如果平衡因子大于0，称为“左重left-heavy”， 小于零称为“右重right-heavy”，平衡因子等于0，则称作平衡。
:::

### AVL实现 python 版
重新定义二叉树中的_put方法即可;


``` python
class TreeNode:
    def __init__(self, key, val, left=None,right=None, parent=None):
        self.key = key;
        self.payload = val;
        self.leftChild = left;
        self.rightChild = right;
        self.parent = parent;
        self.balanceFactor = 0;

def _put(self, key ,val ,currentNode):
    if key < currentNode.key:
        if currentNode.hasLeftChild():
            self._put(key ,val ,currentNode.leftChild); # 递归左子树
        else:
            currentNode.leftChild = TreeNode(key ,val ,parent=currentNode);
            self.updateBalance(currentNode.leftChild);
    else:
        if currentNode.hasRightChild():
            self._put(key ,val ,currentNode.rightChild)  ;# 递归右子树
        else:
            currentNode.rightChild = TreeNode(key ,val ,parent=currentNode);
            self.updateBalance(currentNode.rightChild);


def updateBalance(self,node):
    if node.balanceFactor > 1 or node.balanceFactor < -1:
        self.rebalance(node)
        return
    if node.parent != None:
        if node.isLeftChild():
            node.parent.balanceFactor += 1;
        elif node.isRightChild():
            node.parent.balanceFactor -=1;
            
        if node.parent.balanceFactor !=0:
                self.updateBalance(node.parent)



def rotateLeft(self, rotRoot):
    newRoot = rotRoot.rightChild;
    rotRoot.rightChild = newRoot.leftChild;
    if newRoot.leftChild != None:
        newRoot.leftChild.parent = rotRoot;
    newRoot.parent = rotRoot.parent;
    if rotRoot.isRoot():
        self.root = newRoot;
    else:
        if rotRoot.isLeftChild():
            rotRoot.parent.leftChild = newRoot;
        else:
            rotRoot.parent.rightChild = newRoot;
    newRoot.leftChild = rotRoot;
    rotRoot.parent = newRoot;
    # 仅有两个节点需要调整因子
    rotRoot.balanceFactor = rotRoot.balanceFactor+ 1 - min(newRoot.balanceFactor,0);
    newRoot.balanceFactor = newRoot.balanceFactor+ 1 - min(rotRoot.balanceFactor,0);

def rotateRight(self, rotRoot):
    newRoot = rotRoot.leftChild;
    rotRoot.leftChild = newRoot.rightChild;
    if newRoot.rightChild != None:
        newRoot.rightChild.parent = rotRoot;
    newRoot.parent = rotRoot.parent;
    if rotRoot.isRoot():
        self.root = newRoot;
    else:
        if rotRoot.isRightChild():
            rotRoot.parent.rightChild = newRoot;
        else:
            rotRoot.parent.leftChild = newRoot;
    newRoot.rightChild = rotRoot;
    rotRoot.parent = newRoot;
    # 仅有两个节点需要调整因子
    rotRoot.balanceFactor = rotRoot.balanceFactor - 1 - min(newRoot.balanceFactor, 0);
    rotRoot.balanceFactor = newRoot.balanceFactor - 1 - min(rotRoot.balanceFactor, 0);

def rebalance(self,node):
    if node.balanceFactor < 0:
        if node.rightChild.balanceFactor > 0:
            self.rotateRight(node.rightChild);
            self.rotateLeft(node);
        else:
            self.rotateLeft(node)
    elif node.balanceFactor > 0:
        if node.leftChild.balanceFactor < 0:
            self.rotateLeft(node.leftChild);
            self.rotateRight(node);
        else:
            self.rotateRight(node)

```

### AVL 总结
- get方法也始终保持O(log n)高性能
- 需要插入的新节点是叶节点，更新其所有父节点 和祖先节点的代价最多为O(log n)
- 如果插入的新节点引发了不平衡，重新平衡最多 需要2次旋转，但旋转的代价与问题规模无关， 是常数O(1)
- 所以整个put方法的时间复杂度还是O(log n)